Cite this Article
Sharafat Rajput Ramiz, Pu Cunlai, Li Jie, Chen Rongbin, Xu Zhongqi. Multiple-predators-based capture process on complex networks. Chinese Physics B, 2017, 26(3): 038901  
Permissions
Multiple-predators-based capture process on complex networks
Sharafat Rajput Ramiz1, Pu Cunlai1, 2, †, Li Jie1, Chen Rongbin1, Xu Zhongqi1
Department of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China
Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA

 

† Corresponding author. E-mail: pucunlai@njust.edu.cn

Abstract

The predator/prey (capture) problem is a prototype of many network-related applications. We study the capture process on complex networks by considering multiple predators from multiple sources. In our model, some lions start from multiple sources simultaneously to capture the lamb by biased random walks, which are controlled with a free parameter α. We derive the distribution of the lamb’s lifetime and the expected lifetime 〈T〉. Through simulation, we find that the expected lifetime drops substantially with the increasing number of lions. Moreover, we study how the underlying topological structure affects the capture process, and obtain that locating on small-degree nodes is better than on large-degree nodes to prolong the lifetime of the lamb. The dense or homogeneous network structures are against the survival of the lamb. We also discuss how to improve the capture efficiency in our model.

PACS: 89.75.Hc;05.40.Fb;05.60.Cd
Keyword:capture process;random walk;scale-free networks
1. Introduction

Complex network modeling has been used in many natural and artificial systems, where nodes represent individuals, and edges represent interactions between the individuals. Over the past decade, researchers have made great efforts to study the structural properties of complex networks,[1–3] the dynamical processes existing in complex networks,[4] and the interaction among them.[5,6] For instance, it was found that a variety of complex networks have similar statistical structural properties, such as small-world,[7,8] scale-free,[9,10] high clustering,[11] and so on. Moreover, these general network properties were demonstrated to have great impacts on the network-based problems, such as traffic,[12–16] epidemic spreading,[17–21] network attacks,[22–28] synchronization,[29,30] and control,[31–36] link prediction,[37–39] etc. For example, one of the great findings is that the scale-free networks are robust to random attacks, but very fragile to target attacks.[40] Another breakthrough is that the scale-free networks are proved to have very low (even zero) epidemic thresholds.[41] Also, the results[42,43] show that the combination of short average distance and small standard deviation of degree distribution ensures strong network synchronizability.

Random walk is a basic process related to many of these network problems.[44,45] In graph theory, random walk has been studied for decades, and thus the random walk characteristics like arrival time, meet time, commuting time, cover time, etc.[46,47] have been thoroughly discussed. In recent studies, the random walk theory is used to explore the structures of complex networks such as network sampling,[48] calculating node centrality,[49] detecting cluster structures,[50,51] predicting missing links,[52] etc. Furthermore, random walk has wide applications in communication networks for locating resources,[53] detecting replication attacks,[54] and designing navigation[55,56] or routing protocols.[57] The predator–prey (lion–lamb) model is a common random walk model.[58] In the past, this model was used to illustrate the processes of energy transfer in ecological systems.[59,60] Recently, Sungmin et al.[61] studied the predator–prey model on complex networks, and they particularly focused on how the network structures affect the lamb survival probability. Wang et al.[62] further utilized the predator–prey model in the search problems in point-to-point (P2P) networks. However, in both of their works, there is only one start point of the predator.

In this paper, we generalize the predator–prey model by considering multiple start points of the predators with biased random walks. We first derive the lifetime distribution as well as the expected lifetime of the lamb. Then, we study how the control parameter of the biased random walks and the number of the lions affect the expected lifetime of the lamb. Next, we investigate how the underlying network structure affects the expected lifetime. Finally, we study how to improve the capture efficiency of our model.

2. Model

We use the Price model[63] to generate the underlying scale-free networks. This model contains two steps. (i) Growth: Initially, there are m0 isolated nodes in the network. Then, each time we add a new node to the network with m links going from the new node and pointing to the old ones, where m ≤ m0. (ii) Cumulative advantage: A new node points to an old node i with probability Φi,

(1)
where is the degree of node i, and a is a given constant. Multiple connections from the new node to an old node are not allowed. The process goes N − m0 steps, where N is the desired network size. We ignore the directions of links and obtain the undirected scale-free network. The average node degree is 〈k〉 = 2m, and the power-law parameter is γ = 2 + a/m.

In our capture model, initially some lions start from distinct source nodes to capture a lamb at the destination node. At each time step, every lion steps onto a neighbor node through biased random walk. For instance, a lion at node u steps onto a neighbor node i of u with the transition probability[64,65]

(2)
where kj is the degree of j, and the sum runs over all the neighbor nodes of u. α is a control parameter; when α > 0, the random walk is biased to large-degree nodes, while when α < 0, the random walk is biased to small-degree nodes. When α = 0, the biased random walk is degenerated to simple random walk. The capture process will end when the lamb is captured by the lion which first arrives at the destination node.

3. Analytical results

Assume a graph G(N,M), where N and M represent the sets of nodes and edges, respectively. The adjacency relationship of G can be represented by a matrix A. If there is a link between nodes i and j, then . Here Aij can be taken as the directed weight of the link so that Aij is generally not equal to Aji. When α = 0, Aij = Aji = 1, which is the same as the general adjacency matrix. If there is no link between nodes i and j, Aij = Aji = 0, which is also the same as the general adjacency matrix. Then, the strength of node i is si = ∑Aij. Furthermore, the transition probability matrix is P = K−1A, where K = diag(s1, s2, …, sN). Assuming that at time t = 0, a lion on node u begins to perform the biased random walk, then the probability of reaching node v after t steps of walks can be described as

(3)
where ji is the intermediate node the lion visits at time i. Note that the lion may visit v many times in t steps. According to our model, the capture process ends when the destination node (the location of the lamb) is first visited by the lion. To compute the first arrival time, we set the v-th column of P to be zero, and obtain the new transition probability matrix as
(4)

We can infer through the new transition probability matrix that the probability the lion leaves v after first arriving is zero. Then, we can compute the probability that v has not been visited in the t steps, or in other words, the probability that the lifetime of the lamb is larger than t, which is as follows:

(5)
where Tuv is the time when a lion starting from node u arrives at node v for the first time, which is also the lifetime of the lamb on node v. Next, we assume that initially there are many lions starting from multiple source nodes, which are marked as 1,2,…,z (z < N − 1), and the lamb is still on node v. Note that v is not among the z source nodes. The numbers of lions on the z source nodes are n1,n2,…,nz, respectively. We define as the time when the j-th lion on source node i first arrives at node v. Then, the lifetime of the lamb Tv is the smallest first arrival time of all the lions, which can be described as follows:
(6)

The probability that the lifetime of the lamb is larger than t is

(7)

Since each lion performs independent biased random walks, we have

(8)

Combining Eqs. (5) and (8), we have

(9)

Then, the distribution of the lamb’s lifetime can be calculated as follows

(10)

Finally, the expected lifetime of the lamb is calculated as below:

(11)

The above derivation provides a general method for calculating the expected lifetime for all types of graphs and we have more, simpler calculation methods for special graphs.

3.1. Fully connected graph

Let us consider a fully connected graph, in which each node is connected to every other node with an edge, and thus the degrees of all nodes are identical and equal N − 1. We assume that there are n lions and a lamb randomly distributed in the fully connected graph. Note that, initially, the lions’ sites may be overlapping or not, and the only constraint is that the lamb’s site is not occupied by any lion at the beginning. For this case, we have Prob{T > 0} = 1, , and . Furthermore, we calculate the expected lifetime as follows:

(12)
(13)
(14)

Based on Eq. (13), we have

(15)

Subtracting Eq. (15) from Eq. (14) yields

(16)

Then, we obtain

(17)

According to Eq. (17), when n = 1, 〈T〉 = N − 1, while when n is very large, we have

(18)

From Eq. (18), we can see that the expected lifetime is approximately proportional to the network size and inversely proportional to the number of lions.

3.2. ER random graph

For the ER random graph,[66] the degree distribution obeys the Poisson distribution. We assume that the degrees of all nodes are 〈k〉. We know that for the ER random graph, the probability for any two nodes being connected with an edge is

(19)

Then, we have Prob{T > 0} = 1, and , which are all the same as the fully connected graph. Thus, equations (17) and (18) are also applicable to the ER random graph when 〈k〉 is large. When 〈k〉 is small, approximating 1/ki (the degree of node i) with 1/〈k〉 is not suitable in the calculation. Thus, equations (17) and (18) are not applicable to the ER random graph when 〈k〉 is small.

4. Simulation results

In this section, we mainly study how the lamb’s expected lifetime is affected by the factors in our model such as the control parameter of the biased random walks, the number of the lions, as well as the degree of the node where the lamb locates on. In addition, we investigate how the average node degree and the degree distribution of the underlying networks influence the expected lifetime. Moreover, we discuss the improvement of our capture model with applications to the P2P networks.

First, we study the control parameter α of the biased random walks, and at the same time testify the analytical results by simulation. We use the Price model to generate the underlying scale-free network which contains 100 nodes with an average degree of 4 and a power-law parameter of 2.5, as shown in Fig. 1. Then, we set node 40 as the destination node where the lamb is located, nodes 10 and 90 as the lions’ starting points, on which the numbers of lions are 1 and 2, respectively. We let the lions perform the biased random walks to capture the lamb, and record the lamb’s lifetime. We perform the simulation 104 times and calculate the average (expected) lifetime 〈T〉. The analytical and simulation results are given in Fig. 2. We see that 〈T〉 decreases first and then increases with α, and there is an optimal α (around 0 in Fig. 2) corresponding to the minimum 〈T〉. Moreover, the analytical and simulation results agree very well with each other.

Fig. 1. (color online) A small network generated by the Price model, where N = 100, 〈k〉 = 4, and γ = 2.5. The lamb’s site is node 40, and the lions’ sites are nodes 10 and 90 with one lion on each site.
Fig. 2. (color online) The lamb’s expected lifetime 〈T〉 vs. the parameter α of the biased random walks. The underlying network is shown in Fig. 1. Each data point is the average of 104 independent runs.

Then, we investigate how the number of the lions affects the expected lifetime. In the simulation, we randomly select a node as the lamb’s site and another n lions’ sites with one lion on each site. Under this condition, we perform the capture simulation and calculate the expected lifetime, which is given in Fig. 3(a). Clearly, we can see that 〈T〉 decreases with n abruptly and then converges. Through the above derivation of the lamb’s expected lifetime, we know that the lifetime of the lamb equals the first arrival time of the luckiest lion among all the lions. Generally, the more lions, the smaller the lamb’s lifetime, which agrees with the analytical results of the fully connected graph and the ER random graph (Eq. (18)). Next, we discuss the influence of the degree of the lamb’s site, denoted by klamb. In the simulation, we select the lamb’s site based on its degree, and then randomly select another 10 sites with one lion on each site. The control parameter α is set to be zero. In this case, we calculate the expected lifetime as a function of the degree of the lamb’s site, which is shown in Fig. 3(b). Obviously, we can see that 〈T〉 decreases with increasing klamb, which means that locating on large-degree sites is adverse to the survival of the lamb. In other words, large-degree nodes are easier to visit for random walkers than small-degree nodes, which is also obtained in Ref. [67].

Fig. 3. The lamb’s expected lifetime 〈T〉 vs. (a) the number of lions n and (b) the degree of the lamb’s site klamb. The underlying network is generated by the Price model. The network parameters are the same for panels (a) and (b), which are N = 1000, 〈k〉 = 10, and γ = 2.5. The random walk parameter α equals 0 for both panels. In panel (b), the number of lions n is 10. The details about the sites’ selection for the lamb and lions are illustrated in the text. Each data point is the average of 104 independent runs.

Next, we discuss how the network structure affects the lifetime of the lamb. We focus on the average node degree and the degree distribution, and study one network parameter by fixing the others. In the simulation, we randomly select a node as the lamb’s site, and another 10 nodes as the lions’ sites with one lion on each site. The biased random walk parameter α is set be zero. The simulation results are given in Fig. 4, in which each data point is the average of 104 independent runs. We see a similar trend of the curves of 〈T〉, which go down quickly and then tend to be stable with increasing 〈k〉 in Fig. 4(a) and γ in Fig. 4(b). When the network becomes more dense, the network diameter becomes smaller, which means that the lions and the lamb get closer to each other, and this leads to the decrease of the lamb’s lifetime. When the network is very dense, 〈k〉 does not have a significant influence on 〈T〉, which can also be predicted by Eq. (18). Furthermore, from Fig. 3(b) we know that random walkers are prone to visit large-degree nodes. If the lamb locates on one of the small-degree nodes, which constitute the largest part of the scale-free networks, it is relatively hard for the lions to catch the lamb. Thus, when the network becomes more homogeneous (by increasing γ), the random walkers will visit all nodes more fairly, which increases the capture efficiency or decreases the lamb’s lifetime.

Fig. 4. The lamb’s expected lifetime 〈T〉 vs. (a) the average node degree 〈k〉 and (b) the power-law parameter γ. The underlying networks are generated by the Price model. The parameters are N = 1000, α = 0, and n = 10, with γ = 2.5 for panel (a), and 〈k〉 = 10 for panel (b). The details about the sites’ selection for the lamb and lions are illustrated in the text. Each data point is the average of 104 independent runs.

In our capture model, the lions perform the biased random walks to find the lamb on the network. In fact, the biased random walk mechanism is a basic type, and there are many other random walk mechanisms,[68] such as no-back walk, self-avoiding walk, etc. We can also consider these random walk mechanisms in the capture process. Here we integrate the no-back rule and the self-avoiding rule into our capture model to further improve the capture efficiency. In the improved models, the lions perform biased random walks simultaneously, and obey no-back and self-avoiding rules as well. When considering the no-back rule, a lion will avoid visiting the node which is the last visited node at the next time step unless there is no other choice. When considering the self-avoiding rule, the lion will avoid visiting the nodes which have been visited before at the next time step unless there is no other choice. We compare our original capture model with the modified capture models with the two rules on the P2P network,[69] since the capture model is one of the prototypes of the search problems in P2P networks. The P2P network used in the experiment originally has 6301 nodes and 20777 edges. We process the P2P network by ignoring the directions of the edges and deleting the smaller isolated cluster (which consists of two connected nodes), and finally obtain a connected network with 6299 nodes and 20776 edges. In each run, the lions are located at the four largest-degree nodes with one lion at each node, the site of the lamb is selected among the nodes of degree klamb. The biased random walk parameter α is fixed to be −1. For each klamb, the models run 104 times and the average lamb’s lifetime 〈T〉 is calculated. In Fig. 5, we can see that T decreases with klamb for all the three models. Both the no-back rule and self-avoiding rule improve the capture efficiency since they result in a smaller lifetime of the lamb compared to that of our original capture model, and the self-avoiding rule is better than the no-back rule in terms of the capture efficiency.

Fig. 5. (color online) The lamb’s expected lifetime 〈T〉 vs. the degree of the lamb’s site klamb on the P2P network, which has 6299 nodes and 20776 edges. In each run, the lions are initially located at the four largest-degree nodes with one lion at each node, and we randomly select a node of degree klamb as the site of the lamb with the constraint that the site of the lamb and the sites of the lions cannot be overlapped, and then we conduct the capture simulation. The biased random walk parameter α is −1 for all three models. For each degree klamb, the results are the average of 104 independent runs.
5. Discussion and conclusion

In summary, we study a new kind of capture process, in which there are many lions starting from different source nodes. In detail, we derive the distribution of the lamb’s lifetime as well as the expected lifetime. For the fully connected graph and the ER random graph, we provide a simple approximate calculation of the expected lifetime, and find that the expected lifetime is proportional to the network size and inversely proportional to the number of lions. Next, we study how the factors in our model affect the capture process on scale-free networks by simulation. We find that different values of the biased random walk parameter lead to different capture efficiencies. Generally, given the source and destination nodes, there is always an optimal parameter corresponding to the smallest lifetime, or the highest capture efficiency. Furthermore, we obtain that the more lions, the faster to capture the lamb; especially when the number of lions is small, a few more lions results in a large improvement of the capture efficiency. We also find that the larger the degree of the lamb’s site, the smaller the expected lifetime. Then, we study how the network structure affects the capture process by simulation. We find that the more dense or the more homogeneous the underlying network is, the smaller the lifetime of the lamb is. Finally, we improve our model by considering the no-back rule and the self-avoiding rule with applications to the P2P networks. It is worth mentioning that our model has the potential to be used in many other scenarios, such as the identification of disease genes.[70] We can set the source nodes of lions as the known disease genes associated with a hereditary disorder, then the destination node where the lamb has the smallest lifetime can be another unknown disease gene with large probability.

Reference
[1] Barabási A L 2016 Network Science Cambridge Cambridge University Press
[2] Boccaletti S Bianconi G Criado R 2014 Phys. Rep. 544 1
[3] Mendes J F F Dorogovtsev S N Goltsev A V 2014 Summer Solstice 2014 27
[4] Barrat A Barthelemy M Vespignani A 2008 Dynamical Processes on Complex Networks Cambridge Cambridge University Press
[5] Granell C Gómez S Arenas A 2013 Phys. Rev. Lett. 111 128701
[6] Caldarelli G Vespignani A 2007 Large Scale Structure and Dynamics of Complex Networks Sigapore World Scientific
[7] Watts D J Strogatz S H 1998 Nature 393 440
[8] Muldoon S F Bridgeford E W Bassett D S 2006 Sci. Rep. 6 22057
[9] Barabási A L 2009 Science 325 412
[10] Timár G Dorogovtsev S N Mendes J F F 2016 Phys. Rev. E 94 022302
[11] Albert R Barabási A L 2002 Rev. Mod. Phys. 74 47
[12] Yan G Zhou T Hu B 2006 Phys. Rev. E 73 046108
[13] Wang W X Wang B H Yin C Y 2006 Phys. Rev. E 73 026111
[14] Solé-Ribalta A Gómez S Arenas A 2016 Phys. Rev. Lett. 116 108701
[15] Du W B Zhou X L Jusup M 2016 Sci. Rep. 6 19059
[16] Pu C Li S Yang X 2016 Physica A 447 261
[17] Pastor-Satorras R Castellano C Van Mieghem P 2015 Rev. Mod. Phys. 87 925
[18] Shen Z Cao S Wang W X 2016 Phys. Rev. E 93 032301
[19] Pu C Li S Yang X X 2016 Physica A 446 129
[20] Pu C Li S Yang J 2015 Physica A 432 230
[21] Yang H X Tang M Lai Y C 2015 Phys. Rev. E 91 062817
[22] Min B Do Yi S Lee K M 2014 Phys. Rev. E 89 042811
[23] Pocock M J O Evans D M Memmott J 2012 Science 335 973
[24] Motter A E Lai Y C 2002 Phys. Rev. E 66 065102
[25] Holme P Kim B J Yoon C N 2002 Phys. Rev. E 65 056109
[26] Pu C Li S Michaelson A 2015 Phys. Lett. A 379 1633
[27] Pu C L Cui W 2015 Physica A 419 622
[28] Kovács I A Barabási A L 2015 Nature 524 38
[29] Dörfler F Bullo F 2014 Automatica 50 1539
[30] Lu J Chen G 2005 IEEE Transactions on Automatic Control 50 841
[31] Liu Y Y Slotine J J Barabái A L 2011 Nature 473 167
[32] Ruths J Ruths D 2014 Science 343 1373
[33] Wang X F Chen G 2002 Physica A 310 521
[34] Yan G Tsekenis G Barzel B 2015 Nat. Phys. 11 779
[35] Yuan Z Zhao C Di Z 2013 Nat. Commu. 4 2447
[36] Pu C L Pei W J Michaelson A 2012 Physica A 391 4420
[37] Lü L Zhou T 2011 Physica A 390 1150
[38] Cui W Pu C Xu Z 2016 Physica A 457 202
[39] Xu Z Pu C Yang J 2016 Physica A 456 294
[40] Albert R Jeong H Barabási A L 2000 Nature 406 378
[41] Pastor-Satorras R Vespignani A 2001 Phys. Rev. Lett. 86 3200
[42] Zhao M Zhou T Wang B H Yan G Yang H J Bai W J 2006 Physica A 371 773
[43] Arenas A Díaz-Guilera A Kurths J Moreno Y Zhou C S 2008 Phys. Rep. 469 93
[44] Klafter J Sokolov I M 2011 First Steps in Random Walks: From Tools to Applications Oxford Oxford University Press
[45] White R T 2015 Random Walks on Random Lattices and Their Applications Florida Institute of Technology
[46] Lovász L 1993 Combinatorics, Paul erdos is eighty 2 1
[47] Burioni R Cassi D 2005 J. Phys. A 38 R45
[48] Yoon S Lee S Yook S H 2007 Phys. Rev. E 75 046114
[49] Newman M E J 2005 Soc. Networks 27 39
[50] Rosvall M Bergstrom C T 2008 Proc. Natl. Acad. Sci. 105 1118
[51] Zhou H Distance 2003 Phys. Rev. E 67 061901
[52] Backstrom L Leskovec J 2011 Proceedings of the Fourth ACM International Conference on Web Search and Data Mining. ACM 2011 635
[53] Millán V M L Cholvi V Anta A F 2016 Comp. Net. 103 165
[54] Aalsalem M Y Khan W Z Saad N M 2016 PlOS One 11 e0158072
[55] Fronczak A Fronczak P 2009 Phys. Rev. E 80 016107
[56] Viswanathan G M Buldyrev S V Havlin S 1999 Nature 401 911
[57] Huang B Feng Y Li X 2015 International Conference on Information and Communications Technologies (ICT 2015) IET 2015 1
[58] Berryman A A 1992 Ecology 73 1530
[59] Zumofen G Blumen A 1982 J. Chem. Phys. 76 3713
[60] Barnes C Maxwell D Reuman D C 2010 Ecology 91 222
[61] Lee S Yook S H Kim Y 2006 Phys. Rev. E 74 046118
[62] Wang S P Pei W J 2008 Physica A 387 4699
[63] de Solla Price Derek 1976 J. Am. Soc. Inf. Sci. 27 292
[64] Ou Q Jin Y D Zhou T Wang B H Yin B Q 2007 Phys. Rev. E 75 021102
[65] Yan G Zhou T Wang J Fu Z Q Wang B H 2005 Chin. Phys. Lett. 22 510
[66] Erdös P Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[67] Noh J D Rieger H 2004 Phys. Rev. Lett. 92 118701
[68] Yang S J 2005 Phys. Rev. E 71 016107
[69] Leskovec J Kleinberg J Faloutsos C 2007 ACM Trans. Knowl. Discov. Data (TKDD) 1 2
[70] Köhler S Bauer S Horn D Robinson P N 2008 Am. J. Hum. Genet. 82 949